package sit.engreal.leetcode.problems1000;

import org.junit.jupiter.api.Assertions;

import java.util.ArrayDeque;

/**
 * <a href="https://leetcode.cn/problems/rotting-oranges/">994. 腐烂的橘子</a>
 */
public class LeetCode994 {
    public int orangesRotting(int[][] grid) {
        final ArrayDeque<int[]> deque = new ArrayDeque<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 2) {
                    grid[i][j] = -grid[i][j];
                    deque.addLast(new int[]{i, j});
                }
            }
        }
        int cost = 0;
        for (; ; ) {
            int size = deque.size();
            while (size-- > 0) {
                final int[] p = deque.removeFirst();
                final int i = p[0];
                final int j = p[1];
                if (i - 1 >= 0 && grid[i - 1][j] == 1) {
                    grid[i - 1][j] = -grid[i - 1][j];
                    deque.addLast(new int[]{i - 1, j});
                }
                if (i + 1 < grid.length && grid[i + 1][j] == 1) {
                    grid[i + 1][j] = -grid[i + 1][j];
                    deque.addLast(new int[]{i + 1, j});
                }
                if (j - 1 >= 0 && grid[i][j - 1] == 1) {
                    grid[i][j - 1] = -grid[i][j - 1];
                    deque.addLast(new int[]{i, j - 1});
                }
                if (j + 1 < grid[i].length && grid[i][j + 1] == 1) {
                    grid[i][j + 1] = -grid[i][j + 1];
                    deque.addLast(new int[]{i, j + 1});
                }
            }
            if (deque.isEmpty()) {
                break;
            } else {
                cost++;
            }
        }
        for (int[] cells : grid) {
            for (int cell : cells) {
                if (cell == 1) {
                    return -1;
                }
            }
        }
        return cost;
    }

    public static void main(String[] args) {
        final LeetCode994 demo = new LeetCode994();
        {
            final int[][] grid = {
                    {2, 1, 1},
                    {1, 1, 0},
                    {0, 1, 1}
            };
            Assertions.assertEquals(4, demo.orangesRotting(grid));
        }
        {

            final int[][] grid = {
                    {2, 1, 1},
                    {0, 1, 1},
                    {1, 0, 1}
            };
            Assertions.assertEquals(-1, demo.orangesRotting(grid));
        }

        {

            final int[][] grid = {
                    {0, 2}
            };
            Assertions.assertEquals(0, demo.orangesRotting(grid));
        }
    }
}
